package com.dyz.LeetCodeforSwordFingerOffer;

public class CuttingRope14 {
    //k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？ 动态规划问题
    public int cuttingRope(int n) {
        //base case
        if(n==0){return 0;}
        if(n==1){return 0;}
        if(n==2){return 1;}
        if(n==3){return 2;}
        //一维DP数组
        int[] dp = new int[n+1];

        //base case  //返回于填入值不一样
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4; i<=n;i++){
            //i不切割
            dp[i] = i;
            //i切割, 切成多少段
            for(int j=1; j<=i-1; j++){  //i-1是因为当等于i时相当于不切割
                dp[i] = Math.max(dp[i], j*dp[i-j]);  //注意dp[i-j]
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int aa = new CuttingRope14().cuttingRope(5);
        System.out.println(aa);
    }
}
